package leecode

import "sort"

func subsetsWithDup(nums []int) (result [][]int) {
	sort.Ints(nums)
	path := make([]int, 0, len(nums))
	var backtracking func(startIndex int, used []bool)
	backtracking = func(startIndex int, used []bool) {
		temp := make([]int, len(path))
		copy(temp, path)
		result = append(result, temp)
		for i := startIndex; i < len(nums); i++ {
			//树层去重 当nums[i] == nums[i-1] 时 , 如果直接用的是第二个元素 , 说明在同一层上使用了该元素
			if i > 0 && nums[i] == nums[i-1] && used[i-1] == false {
				continue
			}
			path = append(path, nums[i])
			used[i] = true //true为已使用
			backtracking(i+1, used)
			used[i] = false //回溯
			path = path[:len(path)-1]
		}
	}
	used := make([]bool, len(nums), len(nums))
	used = append(used, false)
	backtracking(0, used)
	return
}
